package 字符串系列;

public class StrStr {
//    public int strStr(String haystack, String needle) {
//        //解法一：java中的indexOf用的是暴力算法，并不是KMP，所以效率不高
//        int a = haystack.indexOf(needle);
//        return a;
//    }
    //解法二：KMP算法，前缀表（减一）Java实现
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }
        //第一步求next数组
        int[] next = new int[needle.length()];
        getNext(next,needle);

        //第二步通过next数组求解
        int j = -1;
        for(int i = 0; i < haystack.length(); i++){
            //1.haystack[i]和needle[j]不相等
            while(j >= 0 && haystack.charAt(i)!=needle.charAt(j+1)){
                j = next[j];    //找到前后缀相等的最大位置
            }
            //2.haystack[i]和needle[j]相等
            if(haystack.charAt(i) == needle.charAt(j+1)){
                j++;    //前缀就可以往前移一位，后缀在循环里会自动移动
            }
            //3.如果子串已经走完了，则返回位置
            if(j==needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }
    public void getNext(int[] next, String s){
        int j = -1;     //j表示前缀末尾，初始化为-1，后续出现错误时，可以直接返回到错误下的next[j],不用返回到next[j-1]
        next[0] = j;    //初始化第一个为-1
        for(int i=1; i<s.length(); i++){    //从1开始是因为当i=0时没有前后缀
            //1.s[j]和s[i]不相等
            while(j >= 0 && s.charAt(i)!=s.charAt(j+1)){
                j = next[j];    //找到前后缀相等的最大位置
            }
            //2.s[j]和s[i]相等
            if(s.charAt(i) == s.charAt(j+1)){
                j++;    //前缀就可以往前移一位，后缀在循环里会自动移动
            }
            //3.修改next数组
            next[i] = j;   //此时的next[i]值修改为匹配的最大前缀
        }
    }
    //解法二：KMP算法，前缀表（不减一）Java实现
    class Solution {
        //前缀表（不减一）Java实现
        public int strStr(String haystack, String needle) {
            if (needle.length() == 0) return 0;
            int[] next = new int[needle.length()];
            getNext(next, needle);

            int j = 0;
            for (int i = 0; i < haystack.length(); i++) {
                while (j > 0 && needle.charAt(j) != haystack.charAt(i))
                    j = next[j - 1];
                if (needle.charAt(j) == haystack.charAt(i))
                    j++;
                if (j == needle.length())
                    return i - needle.length() + 1;
            }
            return -1;

        }

        private void getNext(int[] next, String s) {
            int j = 0;
            next[0] = 0;
            for (int i = 1; i < s.length(); i++) {
                while (j > 0 && s.charAt(j) != s.charAt(i))
                    j = next[j - 1];
                if (s.charAt(j) == s.charAt(i))
                    j++;
                next[i] = j;
            }
        }
    }
}
